{\rtf1\ansi\ansicpg1252\cocoartf1038\cocoasubrtf360
{\fonttbl\f0\fswiss\fcharset0 Helvetica;\f1\froman\fcharset0 Times-Roman;}
{\colortbl;\red255\green255\blue255;}
\paperw11900\paperh16840\margl1440\margr1440\vieww12400\viewh8700\viewkind0
\pard\tx566\tx1133\tx1700\tx2267\tx2834\tx3401\tx3968\tx4535\tx5102\tx5669\tx6236\tx6803\ql\qnatural\pardirnatural

\f0\fs24 \cf0 \
\
Branch prediction:\
\
\
Branch prediction comes into play in superscalar processing.\
Superscalar execution is typically combined with pipelining, \
and so the Fetch/Decode/Rename/Dispatch/Execute/Write out/Retire\
instruction decomposition is made for multiple instructions at once.\
\
Fetch - supply N instructions\
Decode - control signals for N\
Rename - Dependencies between N\
Dispatch - Determine readiness and select N for execution in or out of order\
Execute - allocate enough functional units to execute N instr. + forwarding paths\
Write Out - allocate enough ports to write results of N to registers\
Retire - "clean up" N\
\
\
Branches present a challenge to pipelining (and also in superscalar settings)\
because 1) they occur quite often (15-25% of all insert). This is problematic\
because once a branch instruction is fetched, the next instruction to fetch is not obvious. The actual next instruction can only be determined after N cycles and results in stalling (which reduces IPC). \
\
The problem is critical because even small decreases in prediction accuracy deeply affect performance (in 5-wide superscalar pipeline with 20 cycle branch resolution latency, a 99% accuracy results in 100 cycles for correct path execution and 20 cycles to address the wrong path - 20% extra instructions. 98% - 40% extra,\
95% - 100% extra).\
\
There are many different types of branches, which can be handled differently by a predictor. For instance, unconditional/call/return/indirect jumps will always be taken, and determining the next fetch is resolved at different times (first two during decode because the instruction contains the PC+offset, the last two require register accesses and are only determined during execution). Conditional branches are more problematic not only because the next instruction is only determined during the execution stage, but also because the branch might or might not be taken depending on the result of the conditional.\
\
There are several approaches to the conditional branch handling: branch prediction, branch elimination, multi-path execution, etc. Branch prediction is an attempt to maintain the pipeline full after a branch instruction by determining the likely next instruction to fetch after a branch (needs to determine the direction and target of a branch) during the fetch stage.\
Historically, there are two categories of branch predictors: static and dynamic.                  \
\
Branch Target Buffer/Branch Target Address Cache: target addresses remain the same for conditional direct branches across dynamic instances.\
\
This consists of a cache that is accessed in parallel with the instruction cache during the fetch stage. When a branch is taken, the cache is updated with the target. If BTB hit and the instruction is a predicted-taken branch, target from the BTB is used as a fetch address in the next cycle. If BTB miss or the instruction is a predicted-not-taken branch the next instruction is dictated by the program counter.\
\
Single bit prediction: very simple, too sensitive to the present (no account of past history)\
2BC : more history based, strong prediction does not change with 1 single different outcome (4 state transition system - 2 states predict follow - 2 not).\
\
\
McFarling's "Combining Branch Predictors" (93):\
\
Main idea: Two level branch predictors\
   - First level: N bit branch history register (maintains the direction of last N branches)\
   - Second level: For each configuration of the BHR, maintains a 2BC (Pattern History Table).\
\
 - Variations: BHR can be global, per set of branches, per branch.\
 - PHT counters can be adaptive or static\
 - PHT can be global, per set of branches or per branch.\
\
"An Analysis of Correlation and Predictability: \
What Makes Two-Level Branch Predictors Work" -> analyzes correlations between branches \
\
Interference in PHTs can be a problem (a global BHR means that different branches affect the same PHT entry). \
Solutions:\
 - randomizing (addressing = BHR xor Branch Address)\
 - agree prediction (bias bit in the BTB)\
     -  Conflicting branches become less likely to have opposite predictions (most branches are biased).\
\
Hybrid Predictors:\
\
 - Idea, use multiple predictors and select the "best" one.\
        + better accuracy\
        - More complex (requires selecting the "best")\
        - Longer latency\
\
\
Perceptron predictor:\
   - Learns correlations between branches in the GHR and the current branch using a perceptron\
   - Past branches that are highly correlated have larger weights and influence the outcome more\
\
Enhanced hybrid:\
   - Multi-hybrid with different history lengths\
\
\
\
CALL AND RETURN PREDICTION\
\
\
 - Calls are easy to predict\
     - always taken\
\
 - Returns are indirect (calls occur in multiple points in code)\
      - Multiple possible return points\
      - Usually matches a call\
           - Stack to predict return addresses\
               - Fetch a call: push the next instruction on the stack\
               - Fetch a return: pop the stack and use the address as the predicted target\
               - Very accurate\
\
 INDIRECT BRANCH PREDICTION\
  - register indirect branches have multiple targets\
  - No direction prediction is needed. The difficulty is predicting the address.\
        Idea 1 : Predict the last resolved target as the next fetch address\
            + Use the BTB to store the target address\
	   -  Inaccurate\
\
        Idea 2: Use history based target prediction\
\
\
Summary: \
\
\
   - BTB determines whether a fetched instruction is a branch\
   - Latency (needs to generate next fetch in the next cycle - the bigger the predictor, the slower)\
   - Recovery upon misprediction\
      - Detection only upon execution\
      - Need to flush all younger instructions in the pipeline\
    \
   - Open research issues:\
        - Better algorithms (need to be low cost and fast)\
        - Progressive evaluation of earlier prediction\
               - Prophet-critic hybrid branch prediction\
\
\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\ql\qnatural\pardirnatural

\f1\b\fs28\fsmilli14400 \cf0 An Analysis of Correlation and Predictability: What Makes Two-Level Branch Predictors Work
\f0\b0\fs24 \
\pard\tx566\tx1133\tx1700\tx2267\tx2834\tx3401\tx3968\tx4535\tx5102\tx5669\tx6236\tx6803\ql\qnatural\pardirnatural
\cf0 \
\
\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\ql\qnatural\pardirnatural

\f1\fs20 \cf0 [6] S. Sechrest, C.-C. Lee, and T. Mudge, \'93Correlation and aliasing in dynamic branch predictors,\'94 in 
\i Pro- ceedings of the 23rd Annual International Symposium on Computer Architecture
\i0 , 1996.\
\
T.-Y.YehandY.N.Patt,\'93Alternativeimplementations of two-level adaptive branch prediction,\'94 in 
\i Proceed- ings of the 19th Annual International Symposium on Computer Architecture
\i0 , pp. 124\'96134, 1992.\
\
S. McFarling, \'93Combining branch predictors,\'94 Tech- nical Report TN-36, Digital Western Research Labo- ratory, June 1993.\
\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\ql\qnatural\pardirnatural

\f0\fs24 \cf0 \
\pard\tx566\tx1133\tx1700\tx2267\tx2834\tx3401\tx3968\tx4535\tx5102\tx5669\tx6236\tx6803\ql\qnatural\pardirnatural
\cf0 \
Insights on what makes branches predictable to begin with.\
\

\b \
Dynamic Branch Prediction with Perceptrons\

\b0 \
bi-mode is very good. hybrid is clearly gg.\
\
\
O-GEHL\
\
Optimized Geometric History Length branch predictor.\
"Efficiently exploits very long global histories in the 100-200 bits range"\
\
The BP maintains a collection of tables, the first indexed by the branch\
address, the remaining are indexed by the global history of varying lengths\
(following a geometric series). Related to the perceptron predictor.\
The update is similar but just increments or decrements.\
\
\
\
\
\
}